1. Field of the Invention
The present invention relates to methods and devices for positioning and navigations using dead-reckoning sensor measurements. More particularly, the present invention relates to fusing a plurality of linear and angular displacement measurements from dead-reckoning sensors with mutual calibration and aiding for positioning and navigation.
2. Description of the Prior Art
Dead-reckoning is one of the oldest arts in the human positioning and navigation history. By measuring displacements made over short periods of time, a person can infer his or her current position through adding the displacements up from a known starting point as long as the direction of the displacements is also measured relative to a common reference frame. Sea-goers in the old times threw tethered logs into water and counted the number of knots on the tether rope dragged by the log in the water to estimate the speed relative to the current. The ship's heading was typically determined by the needle of a magnetic compass (or in reference to some known celestial bodies). The floating log and the compass needle (or the visible stars) measure the linear and angular displacements in reference to the water and magnetic north (or the stars in the sky), respectively, and such measurements will be referred to as referenced displacement measurements.
Other examples of referenced displacement measurements include a wheeled odometer, which relies on wheels rolling on the ground to measure the distance traveled along the surface. Recently, the displacement of objects in the image plane (the optical flow) has been used to construct the so-called visual odometer, which enables the measurement of movement of a video camera relative to the imaged objects. A pedometer, which counts the steps when one walks, also provides referenced dead-reckoning measurements. The Doppler principle has also been used to measure the ground velocity of an airborne radar and a laser scanner is used to measure the change in range to stationary objects.
Displacement measurements can also be made without physical interaction with external objects or environments in a self-contained manner. Examples include accelerometers and gyroscopes. Earlier mechanical designs employed a proof mass and a spinning or vibrating mass for measuring linear and angular displacements, respectively. Because of their use of the inertial property of the mass, they are called inertial sensors, which are still used in today's miniature microelectromechanical systems (MEMS). Strictly speaking, inertial sensors interact with the gravity field, which is invisible. Newer designs use fiber optical and ring laser and even atomic gyros.
However, dead-reckoning based navigation solutions experience growing errors due to the accumulation of bias, drift, scale factor, and misalignment errors of the dead-reckoning sensors. Navigation aids (navaids) are frequently used to update the dead-reckoning solutions so as to curb the error growth while calibrating the sensor error terms.
An increasingly popular navigation device is the Global Positioning System (GPS) receiver. As a satellite radio navigation device, GPS provides a reliable, precise, uniform, and stable solution as long as the sky is directly visible. By measuring the distances to at least four GPS satellites, a GPS receiver can solve for the receiver's position location and time offset. The distance, also called pseudorange, is measured in terms of the time for a radio signal to travel from a GPS satellite to the receiver. The time of transmission is encoded in the navigation message modulated on the radio signal whereas the time of arrival (TOA) is obtained from that of the modulating code at the receiver. The time of arrival can be measured to the accuracy of a fraction of a code chip (one chip duration of the coarse acquisition (C/A) code is about 0.978 us or 293 m) or code phase. High-end GPS receivers measure the range in terms of the radio carrier cycles (carrier phase), which is 1540 times (1575.42 MHz vs. 1.023 MHz) shorter than the C/A code chip, thus much more accurate. Since a GPS receiver only measures the carrier phase within a cycle not the whole cycles, advanced algorithms have been developed to solve the integer cycle ambiguity before the carrier phase can be used in ranging for position fixing.
However, GPS solution is severely degraded, if not unavailable at all, in urban and indoor environments, because of the blockage of direct line of sight (LOS) view of GPS satellites. Recently, a number of terrestrial radio signals that are used for broadcast (TV and AM/FM) and wireless communications (cell phone networks) have been used in a way similar to GPS. Since these radio signals are not originally intended (designed) for positioning but are freely available all the time and everywhere (within a certain range) with known characteristics that can be used for positioning, they are often called signals of opportunity (SOOP). Most broadcast and wireless communication signals are designed for use in urban and indoor environments where GPS is most likely to fail.
However, there are serious technical obstacles in positioning with SOOP. Notably, the SOOP transmitters are not synchronized, each subject to a different bias and drift. There is no explicit timing information coded on the signals. At reception, multipath is of serious concern particularly in an urban environment. More importantly, there may not have enough “independent” SOOP, resulting in a rather poor geometric dilution of precision (GDOP).
To solve the problem of not knowing the time of transmission, the idea of using a network of monitor stations installed at known locations that estimate the time of transmission and then send it to users is disclosed by M. Rabinowitz and J. J. Spilker Jr. in the U.S. Pat. No. 6,861,984 entitled, Position Location Using Broadcast Digital Television Signals, issued Mar. 1, 2005. Other methods to deal with unknown times of transmission and to improve poor geometry with few “independent” SOOP are a self-calibration technique disclosed in the U.S. Pat. No. 7,388,541 entitled, Self-Calibrating Position Location Using Periodic Codes in Broadcast Digital Transmissions, issued June 2008 and a cooperative technique disclosed in the U.S. patent application Ser. No. 12/436,868, entitled, Cooperative Position Location Using Periodic Codes in Broadcast Digital Transmissions (May 7, 2009), both by one of the present co-inventors.
Instead of using code-derived range measurements, which needs to solve for the unknown time of transmission, wide-lane techniques that were originally developed for GPS carrier phase were applied to broadcast signals as disclosed by G. Opshaug et al. in the U.S. Pat. No. 7,498,873 entitled, Wide Lane Pesuodrange Measurements Using FM Signals, issued March 2009. Wide lane is in fact a popular technique widely used in GPS to facilitate the integer cycle ambiguity resolution. Temporal carrier phase difference is another technique that actually does not require ambiguity resolution, which was successfully applied to GPS signals as disclosed in the article by F. van Graas and S.-W. Lee entitled, “High-Accuracy Differential Positioning for Satellite-Based Systems without Using Code-Phase Measurements,” appearing in Navigation: Journal of the Institute of Navigation, Vol. 42 No. 4, 1995.
Sequential changes in carrier phase (or phase changes accumulation or accumulated Doppler) can serve as dead reckoning measurements, also noted in a recent magazine column by James L. Farrell entitled, “Between the Lines: A Fortuitous Meeting,” appearing in GPS World (Sep. 24, 2010). This radio dead reckoning actually provides a linear displacement along the radial direction toward the signal source, thus being a referenced dead reckoning measurement. Indeed, simultaneous tracking of three or more fixed radio transmitters enables position location as disclosed by Ell J. Dalabakis and Harry D. Shearer in the U.S. Pat. No. 3,747,106, entitled, Navigation System Utilizing Plural Commercial Broadcast Transmissions, issued Jul. 17, 1973.
However, by itself, riding radio waves for positioning and navigation runs into serious issues in practice particularly in urban environments. One issue is the lack of sufficient independent signal sources to form a good solution geometry. Another issue is the omnipresence of multipath and non-line-of-signal (NLOS) signals. Multipath creates the so-called fading phenomena, which may disrupt signal reception and lead to discontinuity in navigation solution. If NLOS measurements are incorporated into the solution process, the overall navigation accuracy can be severely degraded. Therefore, it is important to identify NLOS multipath signals to exclude them from being used in navigation solution.
Clearly, self-contained and referenced linear and angular displacements measurements from dead-reckoning sensors have their own advantages yet their separate uses are subject to practical difficulties they cannot overcome on their own. A need therefore exists for a positioning and navigation system that combines the advantages of dead-reckoning measurements of complementary nature while providing mutual aiding and calibration to overcome the disadvantages. This need is met by the present invention as described and claimed below.
As compared to the prior art, the present invention introduces a number of innovations. First, it employs the fusion technique that combines temporal carrier phase changes and dead-reckoning sensors to estimate the absolute position, not just the relative position states. Second, it does not require continuous carrier phase tracking, i.e., the methods disclosed herein can operate on intermittently tracked carrier phase measurements. Third, as a general approach, it does not depend on a specific type of signal transmitting system such as GPS. For example, the GPS carrier phase positioning method by F. van Graas and S. W. Lee mentioned earlier approximates the transmitter and user geometry by assuming that the transmitters are far away. The present invention does not make such an assumption. In fact, the use of “close” transmitters actually improves the convergence of the absolute position estimation due to faster geometry changes and explicit inclusion of line-of-sight (LOS) vector error terms that are directly related to the absolute position states. Finally, the disclosed algorithms and methods enable robust operation in dense multipath environments and in the presence of NLOS signals.